This invention relates generally to language translators such as source code compilers and more particularly to translators or source code compilers which reschedule instructions.
As is known in the art, computer language translators such as compilers or assemblers convert a high level language or assembly code into a target language such as machine code which can be used to provide an executable version of a program. In particular, compilers convert high level language computer programs into machine language. That is, a compiler written for a particular high level language and computer converts the particular high level language into a machine language which is specific to the computer, whether that computer is the one on which the compiler resides or another machine.
Because compilers are written with specific hardware systems in mind, many are written to optimize the compiled code such that the compiled code takes advantage of the opportunities presented as a result of the configuration of the computer hardware. For example, in pipelined computer systems and multi-issue machines (super-scalar and very-long-instruction-word computer systems), there are often unused instruction issue slots as a result of data dependencies and resource conflicts between instructions. That is, unused issue slots occur because many instructions take more than one cycle to complete or because data and control dependencies and resource conflicts arise. Thus, while the system is waiting for an instruction to complete it is desirable to make more efficient use of the processor to issue other instructions. One approach which takes advantage of this situation involves rescheduling the order of the computer program instructions at compile time. In this way, a rescheduled instruction may be issued in a slot left empty by a prior instruction.
Typically, compilers break instructions into groups called basic blocks when identifying instructions to reschedule. All instructions in a basic block share the same control dependence. That is, these basic blocks of code have a single entry point and are typically guaranteed to execute all instructions within the block once the block has been entered.
As computers have become capable of executing an increasing number of instructions at a time, these short blocks of code do not provide enough instructions which may be rescheduled to make use of all available issue slots. In order to make additional instructions available for rescheduling, an approach has been developed called "speculative scheduling" which reschedules instructions and places them before branches on which they are control dependent. As a result, a speculatively scheduled instruction is executed before it is known whether it should be executed; that is whether in the logical flow of the program, it would have executed had it not been rescheduled. A speculatively scheduled instruction is called "mispredicted" after it is executed if it is determined that the instruction should not have executed due to a controlling branch taking an unpredicted direction.
During execution of an instruction an exception is raised if the input data to the instruction is invalid. In current implementations, if an instruction was "speculatively scheduled" and therefore "speculatively executed" and the instruction was speculatively scheduled by a compiler or other software mechanism, the exception is generally ignored. On the other hand, if the instruction was speculatively scheduled by hardware, often times the hardware will have circuits which allow the exception to be processed such that the processor can undo errant transactions. If it is shown that an instruction was "mispredicted" (i.e., that it should not have executed) then the exception should be ignored.
As mentioned above, both hardware and software techniques have been developed for speculatively executing instructions. Using a hardware technique, it is expected that the hardware will undo all side effects of mispredicted instructions and that no exception caused by a speculatively scheduled instruction will be raised until it is shown that the instruction was predicted correctly.
One problem with software techniques for speculatively scheduling instructions is that these techniques generally do not have the capability to defer exceptions caused by speculatively scheduled instructions. Therefore, software techniques either confine rescheduling to instructions that cannot generate an exception (i.e. those instructions which, due to hardware constraints, are incapable of raising an exception) or ignore all exceptions that might be generated by speculatively scheduled instructions. As a result, the benefits presently available through software techniques which speculatively schedule instructions are limited. As mentioned above, those software techniques that do attempt to reschedule instructions capable of generating exceptions typically ignore all exceptions whether the instructions are mispredicted or not.